package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

/**
 * verify if the numbers in a arrays can be nodes in a sort tree, and the arrays number is in mid order.
 */
public class VerifyArrayIsASortTree {
    public static boolean veriftArray(int[] array){
        return verifyArray(array,0,array.length-1);
    }

    private static boolean verifyArray(int[] array, int start, int end){
//        System.out.println("log: start:"+start + ":end:"+end);
        int indexForGreater = start;
        if(end-start<2){
            return true;
        }

        while (indexForGreater<end){
            if(array[indexForGreater]>array[end]){
                break;
            }
            indexForGreater++;
        }
        for(int i=indexForGreater; i<end;i++){
            if(array[i]<array[end]){
                return false;
            }
        }
        return verifyArray(array, start, indexForGreater-1)&&verifyArray(array , indexForGreater, end-1);
    }

    public static void main(String[] args){
        System.out.println("result:"+veriftArray(new int[]{1,7,6,9,11,10,5}));
        System.out.println("result:"+veriftArray(new int[]{7,4,6,5}));
    }

}
